package sortingAdvance.quickSort2Ways;

import sortingAdvance.quickSort.InsertionSort;
import sortingAdvance.quickSort.SortTestHelper;

/**
 * 快速排序针对几乎有序数组的处理
 * mxf
 * 2018年5月25日15:53:08
 */
public class QuickSortDealWithNearlyOrderedArray {

    public static void sort(Comparable[] arr) {
        int length  = arr.length;
        sort(arr, 0, length - 1);
    }

    private static void sort(Comparable[] arr, int l, int r) {

        // 对于小规模数组, 使用插入排序
        if(r - l <= 15) {
            InsertionSort.sort(arr, l, r);
            return;
        }
        int p = partition(arr, l, r);
        sort(arr, l, p - 1);
        sort(arr, p + 1, r);
    }

    private static int partition(Comparable[] arr, int l, int r) {
        // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
        swap( arr, l , (int)(Math.random()*(r-l+1))+l );

        int j = l;
        Comparable v = arr[l];

        // arr[l+1...j] < v ; arr[j+1...i) > v
        for(int i = l + 1; i <= r; i++) {
            if(arr[i].compareTo(v) < 0) {
                j ++;
                swap(arr, j, i);
            }
        }
        swap(arr, j, l);
        return j;
    }

    private static void swap(Comparable[] arr, int l, int r) {
        Comparable v = arr[l];
        arr[l] = arr[r];
        arr[r] = v;
    }

    public static void main(String[] args) {
        Integer[] arr = SortTestHelper.generateRandomArray(100, 0, 100);
        QuickSortDealWithNearlyOrderedArray.sort(arr);
        SortTestHelper.printArray(arr);
    }
}
